package com.wrial.middle;
/*
 * @Author  Wrial
 * @Date Created in 16:14 2020/4/3
 * @Description 整数拆分
 可以使用递归，记忆化搜索，动态规划  对于递归满足重复字问题和最优子结构的都可以转化为记忆化搜索和动态规划
 */

public class LeetCode_343 {

    // 1.递归  结果当然是超时
 /*   public int integerBreak(int n) {
        return helper(n);
    }
    private int helper(int n) {
        int max = -1;
        for (int i = 1; i <= n - 1; i++) {
            // 比如3 分解为 1+2 或 1+1+1  1+2 可再分为1+1+1 但是1*2却是最大的值，所以此处要三个值中取最大
            max = maxNum(max, i * helper(n - i), i * (n - i));
        }
        return max;
    }
    private int maxNum(int max, int i, int i1) {
        return Math.max(max, Math.max(i, i1));
    }

  */
    // 2.记忆化搜索
  /*  int[] memo;
    public int integerBreak(int n) {
        assert (n >= 2);
        memo = new int[n+1];
        memo[1] = 1;
        return helper(n);
    }
    private int helper(int n) {
        if (memo[n]!=0) return memo[n];
        int max = -1;
        for (int i = 1; i <= n - 1; i++) {
            // 比如3 分解为 1+2 或 1+1+1  1+2 可再分为1+1+1 但是1*2却是最大的值，所以此处要三个值中取最大
            max = maxNum(max, i * helper(n - i), i * (n - i));
        }
        // 记录当前n的最优解，当然在递归过程中会不断的记录
        memo[n] = max;
        return memo[n];
    }
    private int maxNum(int max, int i, int i1) {
        return Math.max(max, Math.max(i, i1));
    }

   */
    // 3.动态规划
    public int integerBreak(int n) {
        assert (n >= 2);
        int[] memo = new int[n + 1];
        memo[1] = 1;
        // 将n可以分为什么 i*max（n-i）
        for (int i = 2; i <= n - 1; i++) {

            for (int j = 1; j <= i - 1; j++) {

            }

        }
        return 1;
    }

}
